/*
 * Copyright (C), 2015-2018
 * FileName: Solution060
 * Author:   zhao
 * Date:     2018/12/11 18:47
 * Description: 60. 第k个排列
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈60. 第k个排列〉
 *
 * @author zhao
 * @date 2018/12/11 18:47
 * @since 1.0.1
 */
public class Solution060 {
    /**************************************
     * 题目

     给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

     按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

     "123"
     "132"
     "213"
     "231"
     "312"
     "321"
     给定 n 和 k，返回第 k 个排列。

     说明：

     给定 n 的范围是 [1, 9]。
     给定 k 的范围是[1,  n!]。
     示例 1:

     输入: n = 3, k = 3
     输出: "213"
     示例 2:

     输入: n = 4, k = 9
     输出: "2314"
     **************************************/

    /*************************************
     想法：
     k要先变成k-1，因为现在用的是下标值，是以0开头的，k--;
     用k对(n-1)!取商，结果为数据 余数为下一个数字
     比如n=4,这样排列出来的数据就有[1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124...]
     第一轮：
     可以看到以1开头的有3*2*1 = 6种，同理2.3.4的都是这样
     这样8/6 = 1..2（商为1，余数为2）， 结果数据就是索引为1的2（第0个是1）
     然后把2从数组中移除
     第二轮
     这时候数据把2除外就有[134,143,314,341,413,431]
     可以看到以1开头的有2*1 = 2种，同理3.4的都是这样
     上一把余数是2，所以2/2 = 1..0，结果数据就是索引为1的3（第0个是1）
     第三轮
     这时候数据把2除外就有[14,41]
     可以看到以1开头的有1 =1种，同理4的都是这样
     上一把余数是0，所以0/1 = 0..1，结果数据就是索引为0的1（第0个是1）

     我的做法
     超过99%的测试案例
     时间复杂度/空间复杂度：n/n
     代码执行过程：

     总结：
     k--那里没有想到
     ************************************/
    public String getPermutation(int n, int k) {
        if (n <= 1) {
            return "" + n;
        }
        ArrayList arrayList = new ArrayList();
        for (int i = 1; i <= n; i++) {
            arrayList.add(i);
        }

        StringBuilder result = new StringBuilder();
        int leaf = n;
        k = k - 1;
        while (leaf > 0) {
            // 循环求出(n-1)阶乘
            int val = 1;
            for (int i = 1; i <= leaf - 1; i++) {
                val = val * i;
            }
            // 求出下标索引index
            int index = k / val;
            result.append(arrayList.get(index));
            arrayList.remove(index);
            k = k % val;
            leaf--;
        }
        return result.toString();
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public String better(int n, int k) {
        List<Integer> b = new ArrayList<>();
        int a[] = new int[n];
        int j = 0;

        for (int i = 0; i <= n; i++) {
            b.add(i);
        }

        for (int i = n; i > 0; i--) {
            if (k == 0) {
                for (int g = b.size() - 1; g >= 1; g--) {
                    a[n - i - 1 + g] = b.get(b.size() - g);
                }
                break;
            }
            j = pa(i - 1);
            int l = k / j + 1;
            if (k % j != 0) {
                a[n - i] = b.get(l);
                b.remove(l);
            } else {
                a[n - i] = b.get(l - 1);
                b.remove(l - 1);
            }
            k = k % j;

        }
        String s = integerFormatString(a);
        return s;
    }

    private int pa(int n) {
        int k = 1;
        if (n == 0) {
            return 1;
        }
        for (int i = 1; i <= n; i++) {
            k = k * i;
        }
        return k;
    }

    public static String integerFormatString(int[] a) {
        int len = a.length;
        char[] ch = new char[len];
        for (int i = 0; i < len; i++) {
            switch (a[i]) {
                case 0:
                    ch[i] = '0';
                    break;
                case 1:
                    ch[i] = '1';
                    break;
                case 2:
                    ch[i] = '2';
                    break;
                case 3:
                    ch[i] = '3';
                    break;
                case 4:
                    ch[i] = '4';
                    break;
                case 5:
                    ch[i] = '5';
                    break;
                case 6:
                    ch[i] = '6';
                    break;
                case 7:
                    ch[i] = '7';
                    break;
                case 8:
                    ch[i] = '8';
                    break;
                case 9:
                    ch[i] = '9';
                    break;
                default:
                    break;
            }
        }
        String str = new String(ch);
        return str;
    }
}
